## 桶排序
import math
import numpy
def insertion_sort(array, a):       # 插入排序将元素插入桶内列表
    i = 0
    while i < len(array):
        if array[i] > a:
            break
        i += 1
    array.insert(i, a)
    

def bucket_sort(A):
    # 根据数值中元素的个数来设置桶的个数
    # 每一个桶内是一个存储数值的链表
    bucket_list = [[] for _ in range(len(A))]
    for a in A:
        bucket_num = math.floor(len(A) * a)       # 获得元素对应的桶号
        insertion_sort(bucket_list[bucket_num - 1], a)
    sorted_array = []
    for bucket in bucket_list:
        if len(bucket) > 0:
            sorted_array.extend(bucket)
    return sorted_array

N = 20
A = []
for n in range(N):
    f = round(numpy.random.uniform(0, 1), 2)    # 精确到小数点后两位
    A.append(f)
print(f"Before bucket sort : {A}")
A = bucket_sort(A)
print(f"After bucket sort : {A}")

